package com.liyunhan.StrassenAlgorithm;

/**
 * @Description: Strassen算法实现矩阵相乘
 * @Author: Liyunhan
 * @Date: 2021/11/15 22:56
 */
public class MyStrassen extends CalExecTimeAbs {

    public MyStrassen(int n, double[][] matrix1, double[][] matrix2) {
        super(n, matrix1, matrix2);
    }

    /**
     * 算法执行
     */
    @Override
    public void execAlgorithm() {
        this.strassenMutipleMatrix(this.getN(), this.getMatrix1(), this.getMatrix2(), this.getResMatrix());
    }

    /**
     * 矩阵加法通用操作
     *
     * @param matrix1
     * @param matrix2
     * @param resMatrix
     */
    public void matrixAdd(double[][] matrix1, double[][] matrix2, double[][] resMatrix) {
        for (int i = 0; i < matrix1.length; i++) {
            for (int j = 0; j < matrix1.length; j++) {
                resMatrix[i][j] = matrix1[i][j] + matrix2[i][j];
            }
        }

    }

    /**
     * 矩阵减法通用操作(matrix1 - matrix2)
     *
     * @param matrix1
     * @param matrix2
     * @param resMatrix
     */
    public void matrixSub(double[][] matrix1, double[][] matrix2, double[][] resMatrix) {
        for (int i = 0; i < matrix1.length; i++) {
            for (int j = 0; j < matrix1.length; j++) {
                resMatrix[i][j] = matrix1[i][j] - matrix2[i][j];
            }
        }

    }

    /**
     * strassen算法
     *
     * @param n
     * @param matrix1
     * @param matrix2
     */
    public void strassenMutipleMatrix(int n, double[][] matrix1, double[][] matrix2, double[][] resMatrix) {
        //递归结束条件
        if (n == 1){
            resMatrix[0][0] = matrix1[0][0] * matrix2[0][0];
            return;
        }

        int k = n / 2;
        //定义strassen算法所需子矩阵
        double[][] a = new double[k][k];
        double[][] b = new double[k][k];
        double[][] c = new double[k][k];
        double[][] d = new double[k][k];
        double[][] e = new double[k][k];
        double[][] f = new double[k][k];
        double[][] g = new double[k][k];
        double[][] h = new double[k][k];
        double[][] c1 = new double[k][k];
        double[][] c2 = new double[k][k];
        double[][] c3 = new double[k][k];
        double[][] c4 = new double[k][k];

        double[][] p1 = new double[k][k];
        double[][] p2 = new double[k][k];
        double[][] p3 = new double[k][k];
        double[][] p4 = new double[k][k];
        double[][] p5 = new double[k][k];
        double[][] p6 = new double[k][k];
        double[][] p7 = new double[k][k];

        //临时矩阵
        double[][] tempA = new double[k][k];
        double[][] tempB = new double[k][k];
        //按照步骤处理这些子矩阵
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                a[i][j] = matrix1[i][j];
                b[i][j] = matrix1[i][k + j];
                c[i][j] = matrix1[i + k][j];
                d[i][j] = matrix1[i + k][j + k];

                e[i][j] = matrix2[i][j];
                f[i][j] = matrix2[i][k + j];
                g[i][j] = matrix2[i + k][j];
                h[i][j] = matrix2[i + k][j + k];
            }
        }
        matrixSub(f, h, tempB);
        strassenMutipleMatrix(k, a, tempB, p1);

        matrixAdd(a, b, tempA);
        strassenMutipleMatrix(k, tempA, h, p2);

        matrixAdd(c, d, tempA);
        strassenMutipleMatrix(k, tempA, e, p3);

        matrixSub(g, e, tempB);
        strassenMutipleMatrix(k, d, tempB, p4);

        matrixAdd(a, d, tempA);
        matrixAdd(e, h, tempB);
        strassenMutipleMatrix(k, tempA, tempB, p5);

        matrixSub(b, d, tempA);
        matrixAdd(g, h, tempB);
        strassenMutipleMatrix(k, tempA, tempB, p6);

        matrixSub(a, c, tempA);
        matrixAdd(e, f, tempB);
        strassenMutipleMatrix(k, tempA, tempB, p7);

        matrixAdd(p5, p4, c1);
        matrixSub(c1, p2, c1);
        matrixAdd(c1, p6, c1);

        matrixAdd(p1, p2, c2);

        matrixAdd(p3, p4, c3);

        matrixAdd(p5, p1, c4);
        matrixSub(c4, p3, c4);
        matrixSub(c4, p7, c4);

        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++) {
                resMatrix[i][j] = c1[i][j];
                resMatrix[i][j + k] = c2[i][j];
                resMatrix[i + k][j] = c3[i][j];
                resMatrix[i + k][j + k] = c4[i][j];
            }
    }


}
